// https://leetcode.cn/problems/insert-delete-getrandom-o1/description/?envType=study-plan-v2&envId=top-interview-150

// 算法思路总结：
// 1. 哈希表+数组双数据结构组合
// 2. 哈希表存储值到索引的映射，支持O(1)查找
// 3. 数组存储实际数据，支持O(1)随机访问
// 4. 删除时用末尾元素覆盖，维护数组连续性
// 5. 时间复杂度：所有操作O(1)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <string>
#include <unordered_map>

class RandomizedSet
{
private:
    unordered_map<int, int> hash;
    vector<int> vec;

public:
    RandomizedSet()
    {
    }

    bool insert(int val)
    {
        if (hash.count(val) == 0)
        {
            hash[val] = vec.size();
            vec.push_back(val);

            return true;
        }
        return false;
    }

    bool remove(int val)
    {
        if (hash.count(val) > 0)
        {
            int back = vec.back();
            int index = hash[val];

            vec[index] = back;
            hash[back] = index;

            vec.pop_back();
            hash.erase(val);

            return true;
        }
        return false;
    }

    int getRandom()
    {
        int r = rand() % vec.size();
        return vec[r];
    }
};

int main()
{
    RandomizedSet* obj = new RandomizedSet();

    cout << obj->insert(1) << endl;
    cout << obj->remove(2) << endl;
    cout << obj->getRandom() << endl;

    return 0;
}